/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/license-key-formatting
   @Language: C++
   @Datetime: 19-05-17 11:47
   */

class Solution {
public:
	/**
	 * @param S: a string
	 * @param K: a integer
	 * @return: return a string
	 */
	string licenseKeyFormatting(string &S, int K) {
		// write your code here
		int count=0, pos=0;
		for(int i=S.length(); i--; count+=S[i]!='-');
		string str;
		for(pos=0; pos<S.length() && str.length()<count%K; ++pos)
			if(S[pos]!='-') str.push_back(toupper(S[pos]));
		if(str.length()) str.push_back('-');
		for(int i=pos; i<S.length();){
			for(int j=0; j<K; ++i){
				if(S[i]!='-') {
					str.push_back(toupper(S[i]));
					++j;
				}
			}
			str.push_back('-');
		}
		if(str.back()=='-') str.pop_back();
		return str;
	}
};
